lib/Mi manual de algoritmos/version_actual/src/strings/kmp.cpp

   1 ///////////////////////////////////////////////////////////////
   2 //      Knuth-Morris-Pratt algorithm for string matching     //
   3 //                    Complexity: O(n + m)                   //
   4 ///////////////////////////////////////////////////////////////
   5
   6 // Reports all occurrences of 'needle' in 'haystack'.
   7 void kmp(const string &needle, const string &haystack) {
   8   // Precompute border function
   9   int m = needle.size();
  10   vector<int> border(m + 1);
  11   border[0] = -1;
  12   for (int i = 0; i < m; ++i) {
  13     border[i+1] = border[i];
  14     while (border[i+1] > -1 and
  15            needle[border[i+1]] != needle[i]) {
  16       border[i+1] = border[border[i+1]];
  17     }
  18     border[i+1]++;
  19   }
  20
  21   // Now the actual matching
  22   int n = haystack.size();
  23   int seen = 0;
  24   for (int i = 0; i < n; ++i){
  25     while (seen > -1 and needle[seen] != haystack[i]) {
  26       seen = border[seen];
  27     }
  28     if (++seen == m) {
  29       printf("Needle occurs from %d to %d\n", i - m + 1, i);
  30       seen = border[m];
  31     }
  32   }
  33 }